Pada tahun 1955, beliau memasuki Tentera Perancis dan dihantar ke Algeria semasa Peperangan Kemerdekaan Algeria pada tahun 1957. Selepas perkhidmatannya dalam Tentera Perancis, Conté pulang ke Guinea, yang memperolehi kemerdekaan daripada Perancis pada 2 Oktober 1958, dan diintegrasikan ke dalam tentera baru dengan jawatan sarjan. Pada tahun 1962, beliau belajar di sekolah pegawai Camp Alpha di Conakry. Tidak lama kemudian, beliau dialihkan ke pusat pelatihan artileri Batalion kedua di Kindia. Pada 1 Julai 1963, beliau dinaikkan pangkat sebagai Leftenan Kedua. Dua tahun kemudian beliau dinaikkan lagi pangkat kepada Leftenan. Pada 22 November 1970, sekumpulan orang buangan Guinea menyerang negara ini dari Guinea Portugis (kini Guinea-Bissau) untuk menggulingkan kerajaan Presiden Ahmed Sékou Touré. Conté mengambil bahagian untuk mempertahankan ibu kota dan tentera kerajaan segera menumpaskan penyerangan ini. Atas perkhidmatannya kepada negara, beliau dinaikkan pangkat kepada Kapten pada 27 February 1971. Pada tahun 1973, beliau dilantik sebagai komander bagi zon operasi Boké (di Barat Laut Guinea) untuk membantu pergerakan gerila pro-kemerdekaan, Parti Afrika bagi Kemerdekaan Guinea dan Cape Verde (PAIGC) di Guinea Portugis yang di sebelah. Pada 10 Mei 1975, beliau dilantik sebagai penolong kanan Chief of Staff dalam tentera.

Pada tahun 1977, beliau merupakan ketua delegasi Guinea semasa perundingan yang menyelesaikan satu pertikaian sempadan dengan Guinea-Bissau dan dipilih ke dalam Dewan Negara pada tahun 1980. Selepas itu, beliau mengambil bahagian dalam penziarahan rasmi ke Makkah oleh Parti Demokratik Guinea (PDG) yang memerintah.